package 动态规划;

import java.util.ArrayList;

//https://www.nowcoder.com/practice/2b7995aa4f7949d99674d975489cb7da?tpId=46&tqId=29060&tPage=2&rp=2&ru=/ta/leetcode&qru=/ta/leetcode/question-rankin
public class 三角形 {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if (triangle.isEmpty()){
            return 0;
        }

        for (int i = triangle.size() - 2 ; i >= 0 ; i --){
            for (int j = 0 ; j <= i ; j ++){
                int max = Math.min(triangle.get(i + 1).get(j) , triangle.get(i + 1).get(j + 1)) + triangle.get(i).get(j);
                triangle.get(i).set(j , max);
            }


        }
        return triangle.get(0).get(0);
    }
}
